<!DOCTYPE html>
<html lang=zh>
<head>
    <!-- so meta -->
    <meta charset="utf-8">
    <meta http-equiv="X-UA-Compatible" content="IE=edge">
    <meta name="HandheldFriendly" content="True">
    <meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=5" />
    <meta name="description" content="二叉树遇到一道二叉树的题目时的通用思考过程是： 是否可以通过遍历一遍二叉树得到答案？如果不能的话，是否可以定义一个递归函数，通过子问题（子树）的答案推导出原问题的答案？ 只有后序位置才能通过返回值获取子树的信息。 那么换句话说，一旦你发现题目和子树有关，那大概率要给函数设置合理的定义和返回值，在后序位置写代码了。 每一条二叉树的「直径」长度，就是一个节点的左右子树的最大深度之和 遇到子树问题，首先">
<meta property="og:type" content="article">
<meta property="og:title" content="二叉树">
<meta property="og:url" content="https://danyuan30.gitee.io/2022/03/19/algorithm/binaryTree/index.html">
<meta property="og:site_name" content="柯里的语法糖">
<meta property="og:description" content="二叉树遇到一道二叉树的题目时的通用思考过程是： 是否可以通过遍历一遍二叉树得到答案？如果不能的话，是否可以定义一个递归函数，通过子问题（子树）的答案推导出原问题的答案？ 只有后序位置才能通过返回值获取子树的信息。 那么换句话说，一旦你发现题目和子树有关，那大概率要给函数设置合理的定义和返回值，在后序位置写代码了。 每一条二叉树的「直径」长度，就是一个节点的左右子树的最大深度之和 遇到子树问题，首先">
<meta property="og:locale" content="zh_CN">
<meta property="article:published_time" content="2022-03-19T02:35:04.348Z">
<meta property="article:modified_time" content="2022-03-19T02:35:04.348Z">
<meta property="article:author" content="柯里的语法糖">
<meta property="article:tag" content="二叉树">
<meta name="twitter:card" content="summary">
    
    
      
        
          <link rel="shortcut icon" href="https://codertzm.oss-cn-chengdu.aliyuncs.com/favicon.ico">
        
      
      
        
          <link rel="icon" type="image/png" href="https://codertzm.oss-cn-chengdu.aliyuncs.com/favicon.ico" sizes="192x192">
        
      
      
        
          <link rel="apple-touch-icon" sizes="180x180" href="https://codertzm.oss-cn-chengdu.aliyuncs.com/favicon.ico">
        
      
    
    <!-- title -->
    <title>二叉树</title>
    <!-- styles -->
    
<link rel="stylesheet" href="/css/style.css">

    <!-- persian styles -->
    
    <!-- rss -->
    
    
	<!-- mathjax -->
	
<meta name="generator" content="Hexo 6.0.0"></head>

<body class="max-width mx-auto px3 ltr">
    
      <div id="header-post">
  <a id="menu-icon" href="#" aria-label="Menu"><i class="fas fa-bars fa-lg"></i></a>
  <a id="menu-icon-tablet" href="#" aria-label="Menu"><i class="fas fa-bars fa-lg"></i></a>
  <a id="top-icon-tablet" href="#" aria-label="Top" onclick="$('html, body').animate({ scrollTop: 0 }, 'fast');" style="display:none;"><i class="fas fa-chevron-up fa-lg"></i></a>
  <span id="menu">
    <span id="nav">
      <ul>
        <!--
       --><li><a href="/">首页</a></li><!--
     --><!--
       --><li><a href="/tags/">标签</a></li><!--
     --><!--
       --><li><a href="/categories/">分类</a></li><!--
     --><!--
       --><li><a href="/archives/">归档</a></li><!--
     --><!--
       --><li><a target="_blank" rel="noopener" href="http://github.com/twitzz">项目</a></li><!--
     --><!--
       --><li><a href="/about/">关于</a></li><!--
     --><!--
       --><li><a href="/search/">搜索</a></li><!--
     -->
      </ul>
    </span>
    <br/>
    <span id="actions">
      <ul>
        
        
        <li><a class="icon" aria-label="下一篇" href="/2022/03/16/frontend/%E5%89%8D%E7%AB%AF%E9%9D%A2%E8%AF%95%E5%A4%8D%E4%B9%A0/"><i class="fas fa-chevron-right" aria-hidden="true" onmouseover="$('#i-next').toggle();" onmouseout="$('#i-next').toggle();"></i></a></li>
        
        <li><a class="icon" aria-label="返回顶部" href="#" onclick="$('html, body').animate({ scrollTop: 0 }, 'fast');"><i class="fas fa-chevron-up" aria-hidden="true" onmouseover="$('#i-top').toggle();" onmouseout="$('#i-top').toggle();"></i></a></li>
        <li><a class="icon" aria-label="分享文章" href="#"><i class="fas fa-share-alt" aria-hidden="true" onmouseover="$('#i-share').toggle();" onmouseout="$('#i-share').toggle();" onclick="$('#share').toggle();return false;"></i></a></li>
      </ul>
      <span id="i-prev" class="info" style="display:none;">上一篇</span>
      <span id="i-next" class="info" style="display:none;">下一篇</span>
      <span id="i-top" class="info" style="display:none;">返回顶部</span>
      <span id="i-share" class="info" style="display:none;">分享文章</span>
    </span>
    <br/>
    <div id="share" style="display: none">
      <ul>
  <li><a class="icon" target="_blank" rel="noopener" href="http://www.facebook.com/sharer.php?u=https://danyuan30.gitee.io/2022/03/19/algorithm/binaryTree/"><i class="fab fa-facebook " aria-hidden="true"></i></a></li>
  <li><a class="icon" target="_blank" rel="noopener" href="https://twitter.com/share?url=https://danyuan30.gitee.io/2022/03/19/algorithm/binaryTree/&text=二叉树"><i class="fab fa-twitter " aria-hidden="true"></i></a></li>
  <li><a class="icon" target="_blank" rel="noopener" href="http://www.linkedin.com/shareArticle?url=https://danyuan30.gitee.io/2022/03/19/algorithm/binaryTree/&title=二叉树"><i class="fab fa-linkedin " aria-hidden="true"></i></a></li>
  <li><a class="icon" target="_blank" rel="noopener" href="https://pinterest.com/pin/create/bookmarklet/?url=https://danyuan30.gitee.io/2022/03/19/algorithm/binaryTree/&is_video=false&description=二叉树"><i class="fab fa-pinterest " aria-hidden="true"></i></a></li>
  <li><a class="icon" href="mailto:?subject=二叉树&body=Check out this article: https://danyuan30.gitee.io/2022/03/19/algorithm/binaryTree/"><i class="fas fa-envelope " aria-hidden="true"></i></a></li>
  <li><a class="icon" target="_blank" rel="noopener" href="https://getpocket.com/save?url=https://danyuan30.gitee.io/2022/03/19/algorithm/binaryTree/&title=二叉树"><i class="fab fa-get-pocket " aria-hidden="true"></i></a></li>
  <li><a class="icon" target="_blank" rel="noopener" href="http://reddit.com/submit?url=https://danyuan30.gitee.io/2022/03/19/algorithm/binaryTree/&title=二叉树"><i class="fab fa-reddit " aria-hidden="true"></i></a></li>
  <li><a class="icon" target="_blank" rel="noopener" href="http://www.stumbleupon.com/submit?url=https://danyuan30.gitee.io/2022/03/19/algorithm/binaryTree/&title=二叉树"><i class="fab fa-stumbleupon " aria-hidden="true"></i></a></li>
  <li><a class="icon" target="_blank" rel="noopener" href="http://digg.com/submit?url=https://danyuan30.gitee.io/2022/03/19/algorithm/binaryTree/&title=二叉树"><i class="fab fa-digg " aria-hidden="true"></i></a></li>
  <li><a class="icon" target="_blank" rel="noopener" href="http://www.tumblr.com/share/link?url=https://danyuan30.gitee.io/2022/03/19/algorithm/binaryTree/&name=二叉树&description="><i class="fab fa-tumblr " aria-hidden="true"></i></a></li>
  <li><a class="icon" target="_blank" rel="noopener" href="https://news.ycombinator.com/submitlink?u=https://danyuan30.gitee.io/2022/03/19/algorithm/binaryTree/&t=二叉树"><i class="fab fa-hacker-news " aria-hidden="true"></i></a></li>
</ul>

    </div>
    <div id="toc">
      <ol class="toc"><li class="toc-item toc-level-2"><a class="toc-link" href="#%E4%BA%8C%E5%8F%89%E6%A0%91"><span class="toc-number">1.</span> <span class="toc-text">二叉树</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91-%EF%BC%88BST%EF%BC%89"><span class="toc-number">2.</span> <span class="toc-text">二叉搜索树 （BST）</span></a><ol class="toc-child"><li class="toc-item toc-level-3"><a class="toc-link" href="#%E9%AA%8C%E8%AF%81BST"><span class="toc-number">2.1.</span> <span class="toc-text">验证BST</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#BST%E6%90%9C%E7%B4%A2%E5%85%83%E7%B4%A0"><span class="toc-number">2.2.</span> <span class="toc-text">BST搜索元素</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#BST%E6%8F%92%E5%85%A5%E5%85%83%E7%B4%A0"><span class="toc-number">2.3.</span> <span class="toc-text">BST插入元素</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#BST%E5%88%A0%E9%99%A4%E5%85%83%E7%B4%A0"><span class="toc-number">2.4.</span> <span class="toc-text">BST删除元素</span></a></li></ol></li></ol>
    </div>
  </span>
</div>

    
    <div class="content index py4">
        
        <article class="post" itemscope itemtype="http://schema.org/BlogPosting">
  <header>
    
    <h1 class="posttitle" itemprop="name headline">
        二叉树
    </h1>



    <div class="meta">
      <span class="author" itemprop="author" itemscope itemtype="http://schema.org/Person">
        <span itemprop="name">柯里的语法糖</span>
      </span>
      
    <div class="postdate">
      
        <time datetime="2022-03-19T02:35:04.348Z" itemprop="datePublished">2022-03-19</time>
        
      
    </div>


      
    <div class="article-category">
        <i class="fas fa-archive"></i>
        <a class="category-link" href="/categories/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E4%B8%8E%E7%AE%97%E6%B3%95/">数据结构与算法</a>
    </div>


      
    <div class="article-tag">
        <i class="fas fa-tag"></i>
        <a class="tag-link-link" href="/tags/%E4%BA%8C%E5%8F%89%E6%A0%91/" rel="tag">二叉树</a>
    </div>


    </div>
  </header>
  

  <div class="content" itemprop="articleBody">
    <h2 id="二叉树"><a href="#二叉树" class="headerlink" title="二叉树"></a>二叉树</h2><p>遇到一道二叉树的题目时的通用思考过程是：</p>
<p><strong>是否可以通过遍历一遍二叉树得到答案？如果不能的话，是否可以定义一个递归函数，通过子问题（子树）的答案推导出原问题的答案</strong>？</p>
<p>只有后序位置才能通过返回值获取子树的信息。</p>
<p><strong>那么换句话说，一旦你发现题目和子树有关，那大概率要给函数设置合理的定义和返回值，在后序位置写代码了</strong>。</p>
<p><strong>每一条二叉树的「直径」长度，就是一个节点的左右子树的最大深度之和</strong></p>
<p>遇到子树问题，首先想到的是给函数设置返回值，然后在后序位置做文章。</p>
<figure class="highlight js"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">let</span> maxDiameter = <span class="number">0</span></span><br><span class="line"><span class="keyword">var</span> diameterOfBinaryTree = <span class="function"><span class="keyword">function</span> (<span class="params">root</span>) </span>&#123;</span><br><span class="line">  maxDepth(root)</span><br><span class="line">  <span class="keyword">return</span> maxDiameter</span><br><span class="line">&#125;;</span><br><span class="line"></span><br><span class="line"><span class="keyword">var</span> maxDepth = <span class="function"><span class="keyword">function</span> (<span class="params">root</span>) </span>&#123;</span><br><span class="line">  <span class="keyword">if</span> (root === <span class="literal">null</span>) &#123;</span><br><span class="line">    <span class="keyword">return</span> <span class="number">0</span></span><br><span class="line">  &#125;</span><br><span class="line">  <span class="keyword">let</span> left = maxDepth(root.left)</span><br><span class="line">  <span class="keyword">let</span> right = maxDepth(root.right)</span><br><span class="line">  <span class="keyword">let</span> myDiameter = left + right</span><br><span class="line">  maxDiameter = <span class="built_in">Math</span>.max(myDiameter, maxDiameter)</span><br><span class="line">  <span class="keyword">return</span> <span class="number">1</span> + <span class="built_in">Math</span>.max(left, right)</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<p><strong>写树相关的算法，简单说就是，先搞清楚当前 <code>root</code> 节点「该做什么」以及「什么时候做」，然后根据函数定义递归调用子节点</strong></p>
<p><strong>对于构造二叉树的问题，根节点要做的就是把想办法把自己构造出来</strong>。</p>
<h2 id="二叉搜索树-（BST）"><a href="#二叉搜索树-（BST）" class="headerlink" title="二叉搜索树 （BST）"></a>二叉搜索树 （BST）</h2><p>特性：</p>
<p>1、对于 BST 的每一个节点 <code>node</code>，左子树节点的值都比 <code>node</code> 的值要小，右子树节点的值都比 <code>node</code> 的值大。</p>
<p>2、对于 BST 的每一个节点 <code>node</code>，它的左侧子树和右侧子树都是 BST。</p>
<p><strong>从做算法题的角度来看 BST，除了它的定义，还有一个重要的性质：BST 的中序遍历结果是有序的（升序）</strong>。</p>
<p>二叉搜索树做题的主要思路就是利用这个特性</p>
<p>对于 BST 相关的问题，你可能会经常看到类似下面这样的代码逻辑：</p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">BST</span><span class="params">(TreeNode root, <span class="keyword">int</span> target)</span> </span>&#123;</span><br><span class="line">    <span class="keyword">if</span> (root.val == target)</span><br><span class="line">        <span class="comment">// 找到目标，做点什么</span></span><br><span class="line">    <span class="keyword">if</span> (root.val &lt; target) </span><br><span class="line">        BST(root.right, target);</span><br><span class="line">    <span class="keyword">if</span> (root.val &gt; target)</span><br><span class="line">        BST(root.left, target);</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>



<p><strong>遇到任何递归型的问题，无非就是灵魂三问</strong>：</p>
<p><strong>1、这个函数是干嘛的</strong>？</p>
<p><strong>2、这个函数参数中的变量是什么的是什么</strong>？</p>
<p><strong>3、得到函数的递归结果，你应该干什么</strong>？</p>
<h3 id="验证BST"><a href="#验证BST" class="headerlink" title="验证BST"></a>验证BST</h3><figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br></pre></td><td class="code"><pre><span class="line"><span class="function">boolean <span class="title">isValidBST</span><span class="params">(TreeNode root)</span> </span>&#123;</span><br><span class="line">    <span class="keyword">return</span> <span class="built_in">isValidBST</span>(root, null, null);</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="comment">/* 限定以 root 为根的子树节点必须满足 max.val &gt; root.val &gt; min.val */</span></span><br><span class="line"><span class="function">boolean <span class="title">isValidBST</span><span class="params">(TreeNode root, TreeNode min, TreeNode max)</span> </span>&#123;</span><br><span class="line">    <span class="comment">// base case</span></span><br><span class="line">    <span class="keyword">if</span> (root == null) <span class="keyword">return</span> <span class="literal">true</span>;</span><br><span class="line">    <span class="comment">// 若 root.val 不符合 max 和 min 的限制，说明不是合法 BST</span></span><br><span class="line">    <span class="keyword">if</span> (min != null &amp;&amp; root.val &lt;= min.val) <span class="keyword">return</span> <span class="literal">false</span>;</span><br><span class="line">    <span class="keyword">if</span> (max != null &amp;&amp; root.val &gt;= max.val) <span class="keyword">return</span> <span class="literal">false</span>;</span><br><span class="line">    <span class="comment">// 限定左子树的最大值是 root.val，右子树的最小值是 root.val</span></span><br><span class="line">    <span class="keyword">return</span> <span class="built_in">isValidBST</span>(root.left, min, root) </span><br><span class="line">        &amp;&amp; <span class="built_in">isValidBST</span>(root.right, root, max);</span><br><span class="line">&#125;</span><br><span class="line"></span><br></pre></td></tr></table></figure>

<h3 id="BST搜索元素"><a href="#BST搜索元素" class="headerlink" title="BST搜索元素"></a>BST搜索元素</h3><figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br></pre></td><td class="code"><pre><span class="line"><span class="function">TreeNode <span class="title">searchBST</span><span class="params">(TreeNode root, <span class="keyword">int</span> target)</span> </span>&#123;</span><br><span class="line">    <span class="keyword">if</span> (root == null) &#123;</span><br><span class="line">        <span class="keyword">return</span> null;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="comment">// 去左子树搜索</span></span><br><span class="line">    <span class="keyword">if</span> (root.val &gt; target) &#123;</span><br><span class="line">        <span class="keyword">return</span> <span class="built_in">searchBST</span>(root.left, target);</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="comment">// 去右子树搜索</span></span><br><span class="line">    <span class="keyword">if</span> (root.val &lt; target) &#123;</span><br><span class="line">        <span class="keyword">return</span> <span class="built_in">searchBST</span>(root.right, target);</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> root;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<h3 id="BST插入元素"><a href="#BST插入元素" class="headerlink" title="BST插入元素"></a>BST插入元素</h3><figure class="highlight js"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br></pre></td><td class="code"><pre><span class="line">TreeNode <span class="function"><span class="title">insertIntoBST</span>(<span class="params">TreeNode root, int val</span>)</span> &#123;</span><br><span class="line">    <span class="comment">// 找到空位置插入新节点</span></span><br><span class="line">    <span class="keyword">if</span> (root == <span class="literal">null</span>) <span class="keyword">return</span> <span class="keyword">new</span> TreeNode(val);</span><br><span class="line">    <span class="comment">// if (root.val == val)</span></span><br><span class="line">    <span class="comment">//     BST 中一般不会插入已存在元素</span></span><br><span class="line">    <span class="keyword">if</span> (root.val &lt; val) </span><br><span class="line">        root.right = insertIntoBST(root.right, val);</span><br><span class="line">    <span class="keyword">if</span> (root.val &gt; val) </span><br><span class="line">        root.left = insertIntoBST(root.left, val);</span><br><span class="line">    <span class="keyword">return</span> root;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<h3 id="BST删除元素"><a href="#BST删除元素" class="headerlink" title="BST删除元素"></a>BST删除元素</h3><figure class="highlight js"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br></pre></td><td class="code"><pre><span class="line">TreeNode <span class="function"><span class="title">deleteNode</span>(<span class="params">TreeNode root, int key</span>)</span> &#123;</span><br><span class="line">    <span class="keyword">if</span> (root == <span class="literal">null</span>) <span class="keyword">return</span> <span class="literal">null</span>;</span><br><span class="line">    <span class="keyword">if</span> (root.val == key) &#123;</span><br><span class="line">        <span class="comment">// 这两个 if 把情况 1 和 2 都正确处理了</span></span><br><span class="line">        <span class="keyword">if</span> (root.left == <span class="literal">null</span>) <span class="keyword">return</span> root.right;</span><br><span class="line">        <span class="keyword">if</span> (root.right == <span class="literal">null</span>) <span class="keyword">return</span> root.left;</span><br><span class="line">        <span class="comment">// 处理情况 3</span></span><br><span class="line">        <span class="comment">// 获得右子树最小的节点</span></span><br><span class="line">        TreeNode minNode = getMin(root.right);</span><br><span class="line">        <span class="comment">// 删除右子树最小的节点</span></span><br><span class="line">        root.right = deleteNode(root.right, minNode.val);</span><br><span class="line">        <span class="comment">// 用右子树最小的节点替换 root 节点</span></span><br><span class="line">        minNode.left = root.left;</span><br><span class="line">        minNode.right = root.right;</span><br><span class="line">        root = minNode;</span><br><span class="line">    &#125; <span class="keyword">else</span> <span class="keyword">if</span> (root.val &gt; key) &#123;</span><br><span class="line">        root.left = deleteNode(root.left, key);</span><br><span class="line">    &#125; <span class="keyword">else</span> <span class="keyword">if</span> (root.val &lt; key) &#123;</span><br><span class="line">        root.right = deleteNode(root.right, key);</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> root;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line">TreeNode <span class="function"><span class="title">getMin</span>(<span class="params">TreeNode node</span>)</span> &#123;</span><br><span class="line">    <span class="comment">// BST 最左边的就是最小的</span></span><br><span class="line">    <span class="keyword">while</span> (node.left != <span class="literal">null</span>) node = node.left;</span><br><span class="line">    <span class="keyword">return</span> node;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>


  </div>
</article>



        
          <div id="footer-post-container">
  <div id="footer-post">

    <div id="nav-footer" style="display: none">
      <ul>
         
          <li><a href="/">首页</a></li>
         
          <li><a href="/tags/">标签</a></li>
         
          <li><a href="/categories/">分类</a></li>
         
          <li><a href="/archives/">归档</a></li>
         
          <li><a target="_blank" rel="noopener" href="http://github.com/twitzz">项目</a></li>
         
          <li><a href="/about/">关于</a></li>
         
          <li><a href="/search/">搜索</a></li>
        
      </ul>
    </div>

    <div id="toc-footer" style="display: none">
      <ol class="toc"><li class="toc-item toc-level-2"><a class="toc-link" href="#%E4%BA%8C%E5%8F%89%E6%A0%91"><span class="toc-number">1.</span> <span class="toc-text">二叉树</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91-%EF%BC%88BST%EF%BC%89"><span class="toc-number">2.</span> <span class="toc-text">二叉搜索树 （BST）</span></a><ol class="toc-child"><li class="toc-item toc-level-3"><a class="toc-link" href="#%E9%AA%8C%E8%AF%81BST"><span class="toc-number">2.1.</span> <span class="toc-text">验证BST</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#BST%E6%90%9C%E7%B4%A2%E5%85%83%E7%B4%A0"><span class="toc-number">2.2.</span> <span class="toc-text">BST搜索元素</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#BST%E6%8F%92%E5%85%A5%E5%85%83%E7%B4%A0"><span class="toc-number">2.3.</span> <span class="toc-text">BST插入元素</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#BST%E5%88%A0%E9%99%A4%E5%85%83%E7%B4%A0"><span class="toc-number">2.4.</span> <span class="toc-text">BST删除元素</span></a></li></ol></li></ol>
    </div>

    <div id="share-footer" style="display: none">
      <ul>
  <li><a class="icon" target="_blank" rel="noopener" href="http://www.facebook.com/sharer.php?u=https://danyuan30.gitee.io/2022/03/19/algorithm/binaryTree/"><i class="fab fa-facebook fa-lg" aria-hidden="true"></i></a></li>
  <li><a class="icon" target="_blank" rel="noopener" href="https://twitter.com/share?url=https://danyuan30.gitee.io/2022/03/19/algorithm/binaryTree/&text=二叉树"><i class="fab fa-twitter fa-lg" aria-hidden="true"></i></a></li>
  <li><a class="icon" target="_blank" rel="noopener" href="http://www.linkedin.com/shareArticle?url=https://danyuan30.gitee.io/2022/03/19/algorithm/binaryTree/&title=二叉树"><i class="fab fa-linkedin fa-lg" aria-hidden="true"></i></a></li>
  <li><a class="icon" target="_blank" rel="noopener" href="https://pinterest.com/pin/create/bookmarklet/?url=https://danyuan30.gitee.io/2022/03/19/algorithm/binaryTree/&is_video=false&description=二叉树"><i class="fab fa-pinterest fa-lg" aria-hidden="true"></i></a></li>
  <li><a class="icon" href="mailto:?subject=二叉树&body=Check out this article: https://danyuan30.gitee.io/2022/03/19/algorithm/binaryTree/"><i class="fas fa-envelope fa-lg" aria-hidden="true"></i></a></li>
  <li><a class="icon" target="_blank" rel="noopener" href="https://getpocket.com/save?url=https://danyuan30.gitee.io/2022/03/19/algorithm/binaryTree/&title=二叉树"><i class="fab fa-get-pocket fa-lg" aria-hidden="true"></i></a></li>
  <li><a class="icon" target="_blank" rel="noopener" href="http://reddit.com/submit?url=https://danyuan30.gitee.io/2022/03/19/algorithm/binaryTree/&title=二叉树"><i class="fab fa-reddit fa-lg" aria-hidden="true"></i></a></li>
  <li><a class="icon" target="_blank" rel="noopener" href="http://www.stumbleupon.com/submit?url=https://danyuan30.gitee.io/2022/03/19/algorithm/binaryTree/&title=二叉树"><i class="fab fa-stumbleupon fa-lg" aria-hidden="true"></i></a></li>
  <li><a class="icon" target="_blank" rel="noopener" href="http://digg.com/submit?url=https://danyuan30.gitee.io/2022/03/19/algorithm/binaryTree/&title=二叉树"><i class="fab fa-digg fa-lg" aria-hidden="true"></i></a></li>
  <li><a class="icon" target="_blank" rel="noopener" href="http://www.tumblr.com/share/link?url=https://danyuan30.gitee.io/2022/03/19/algorithm/binaryTree/&name=二叉树&description="><i class="fab fa-tumblr fa-lg" aria-hidden="true"></i></a></li>
  <li><a class="icon" target="_blank" rel="noopener" href="https://news.ycombinator.com/submitlink?u=https://danyuan30.gitee.io/2022/03/19/algorithm/binaryTree/&t=二叉树"><i class="fab fa-hacker-news fa-lg" aria-hidden="true"></i></a></li>
</ul>

    </div>

    <div id="actions-footer">
        <a id="menu" class="icon" href="#" onclick="$('#nav-footer').toggle();return false;"><i class="fas fa-bars fa-lg" aria-hidden="true"></i> 菜单</a>
        <a id="toc" class="icon" href="#" onclick="$('#toc-footer').toggle();return false;"><i class="fas fa-list fa-lg" aria-hidden="true"></i> 目录</a>
        <a id="share" class="icon" href="#" onclick="$('#share-footer').toggle();return false;"><i class="fas fa-share-alt fa-lg" aria-hidden="true"></i> 分享</a>
        <a id="top" style="display:none" class="icon" href="#" onclick="$('html, body').animate({ scrollTop: 0 }, 'fast');"><i class="fas fa-chevron-up fa-lg" aria-hidden="true"></i> 返回顶部</a>
    </div>

  </div>
</div>

        
        <footer id="footer">
  <div class="footer-left">
    Copyright &copy;
    
    
    2021-2022
    柯里的语法糖
  </div>
  <div class="footer-right">
    <nav>
      <ul>
        <!--
       --><li><a href="/">首页</a></li><!--
     --><!--
       --><li><a href="/tags/">标签</a></li><!--
     --><!--
       --><li><a href="/categories/">分类</a></li><!--
     --><!--
       --><li><a href="/archives/">归档</a></li><!--
     --><!--
       --><li><a target="_blank" rel="noopener" href="http://github.com/twitzz">项目</a></li><!--
     --><!--
       --><li><a href="/about/">关于</a></li><!--
     --><!--
       --><li><a href="/search/">搜索</a></li><!--
     -->
      </ul>
    </nav>
  </div>
</footer>

    </div>
    <!-- styles -->



  <link rel="preload" as="style" href="https://cdnjs.cloudflare.com/ajax/libs/font-awesome/5.15.2/css/all.min.css" crossorigin="anonymous" onload="this.onload=null;this.rel='stylesheet'"/>


    <!-- jquery -->
 
  <script src="https://cdnjs.cloudflare.com/ajax/libs/jquery/3.6.0/jquery.min.js" crossorigin="anonymous"></script> 




<!-- clipboard -->

  
    <script src="https://cdnjs.cloudflare.com/ajax/libs/clipboard.js/2.0.7/clipboard.min.js" crossorigin="anonymous"></script> 
  
  <script type="text/javascript">
  $(function() {
    // copy-btn HTML
    var btn = "<span class=\"btn-copy tooltipped tooltipped-sw\" aria-label=\"复制到粘贴板!\">";
    btn += '<i class="far fa-clone"></i>';
    btn += '</span>'; 
    // mount it!
    $(".highlight table").before(btn);
    var clip = new ClipboardJS('.btn-copy', {
      text: function(trigger) {
        return Array.from(trigger.nextElementSibling.querySelectorAll('.code')).reduce((str,it)=>str+it.innerText+'\n','')
      }
    });
    clip.on('success', function(e) {
      e.trigger.setAttribute('aria-label', "复制成功!");
      e.clearSelection();
    })
  })
  </script>


<script src="/js/main.js"></script>

<!-- search -->

<!-- Google Analytics -->

<!-- Baidu Analytics -->

<!-- Cloudflare Analytics -->

<!-- Umami Analytics -->

<!-- Disqus Comments -->

<!-- utterances Comments -->

</body>
</html>
